#include <iostream>
#include <vector>
using namespace std;

class RandomizedSet {
public:
    RandomizedSet() {
        srand((unsigned int)time(NULL));
    }

    bool insert(int val) {
        for (int i = 0; i < n; i++)
        {
            if (p[i] == val)
            {
                return false;
            }
        }
        p.push_back(val);
        n++;
        return true;
    }

    bool remove(int val) {
        for (int i = 0; i < n; i++)
        {
            if (p[i] == val)
            {
                for (int k = i; k < n - 1; k++)
                {
                    p[k] = p[k + 1];
                }
                this->n--;
                return true;
            }
        }
        return false;
    }

    int getRandom() {
        return p[rand() % n];
    }
private:
    vector<int> p;
    int n = 0;
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ret;
        int n = nums.size();
        int sum = 1;
        for (int i = 0; i < n; i++)
        {
            for (int k = 0; k < n; k++)
            {
                if (i == k)
                {
                    continue;
                }
                if (nums[k] == 0)
                {
                    sum = 0;
                    break;
                }
                else
                {
                    sum *= nums[k];
                }
            }
            ret.push_back(sum);
            sum = 1;
        }
        return ret;
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ret;
        int n = nums.size();
        int sum = 1;
        int p = 0;
        for (int i = 0; i < n; i++)
        {
            if (nums[i] == 0)
            {
                p++;
                if (p > 2)
                {
                    sum = 0;
                    break;
                }
                continue;
            }
            sum *= nums[i];
        }
        for (int i = 0; i < n; i++)
        {
            if (p == 1 && nums[i] == 0)
            {
                ret.push_back(sum);
            }
            else if (p > 1)
            {
                ret.push_back(0);
            }
            else if (p == 1 && nums[i] != 0)
            {
                ret.push_back(0);
            }
            else
            {
                ret.push_back(sum / nums[i]);
            }
        }
        return ret;
    }
};

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            if (gas[i] < cost[i])
            {
                continue;
            }
            int k = i + 1;
            if (k == n)
            {
                k = 0;
            }
            sum = gas[i] - cost[i];
            while (k >= 0)
            {
                sum = sum + gas[k] - cost[k];
                if (sum < 0)
                {
                    break;
                }
                k++;
                if (k == i)
                {
                    return i;
                }
                if (k == n)
                {
                    k = 0;
                }
            }
        }
        return -1;
    }
};

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = 0;
        int n2 = 0;
        int n = nums1.size() + nums2.size();
        double ret = 0;
        int p = n / 2;
        int index = 0;
        while (n1 < nums1.size() && n2 < nums2.size())
        {
            if (nums1[n1] < nums2[n2])
            {
                if ((index == p - 1 && n % 2 == 0) || index == p)
                {
                    ret += nums1[n1];
                }
                n1++;
                index++;
            }
            else
            {
                if ((index == p - 1 && n % 2 == 0) || index == p)
                {
                    ret += nums2[n2];
                }
                n2++;
                index++;
            }
        }
        while (n1 < nums1.size())
        {
            if ((index == p - 1 && n % 2 == 0) || index == p)
            {
                ret += nums1[n1];
            }
            n1++;
            index++;
        }
        while (n2 < nums2.size())
        {
            if ((index == p - 1 && n % 2 == 0) || index == p)
            {
                ret += nums2[n2];
            }
            n2++;
            index++;
        }
        if (n % 2 == 0)
        {
            ret /= 2;
        }
        return ret;
    }
};

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr)
        {
            return 0;
        }
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr)
        {
            return true;
        }
        else if (p == nullptr && q != nullptr)
        {
            return false;
        }
        else if (p != nullptr && q == nullptr)
        {
            return false;
        }
        if (p->val == q->val)
        {
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        }
        return false;
    }
};

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr)
        {
            return nullptr;
        }
        TreeNode* left = invertTree(root->right);
        TreeNode* right = invertTree(root->left);
        root->left = left;
        root->right = right;
        return root;
    }
};

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q)
    {
        if (p == nullptr && q == nullptr)
        {
            return true;
        }
        else if (p == nullptr && q != nullptr)
        {
            return false;
        }
        else if (p != nullptr && q == nullptr)
        {
            return false;
        }
        if (p->val == q->val)
        {
            return isSameTree(p->left, q->right) && isSameTree(p->right, q->left);
        }
        return false;
    }
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr)
        {
            return true;
        }
        return isSameTree(root->left, root->right);
    }
};